package com.huang.leetcode.tree;

import com.huang.leetcode.constant.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @Author：CreateSequence
 * @Date：2020-07-24 21:43
 * @Description：二叉树的中序遍历
 */
public class PB94 {

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<TreeNode>();

        while (stack.size() > 0 || root != null) {
            //持续向左树查找并将值入栈，直到走到底
            if (root != null) {
                stack.push(root);
                root = root.left;
            }else {
                //左树到底了将栈顶元素出栈并输出，也就是回去上一个节点
                //然后转向上一个节点的左节点，接着重复上述过程
                TreeNode temp = stack.pop();
                res.add(temp.val);
                root = temp.right;
            }
        }
        return res;
    }

}
